package com.fang.algorithm.leecode;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位 数字。
 * <p>
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头
 * <p>
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * <p>
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * @date 2022/5/19 12:35 下午
 **/
public class L2_AddTwoLinkedList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        ListNode node2 = new ListNode(2);
        node2.next = new ListNode(9);
        node2.next.next = new ListNode(8);
        printNode(node1);
        printNode(node2);
        ListNode addNode = addTwoNumbers(node1, node2);
        printNode(addNode);
    }

    private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1.计算链表的长度作为基准作为链表头
        int length1 = calcNodeLength(l1);
        int length2 = calcNodeLength(l2);
        ListNode head1 = length1 >= length2 ? l1 : l2;
        ListNode head2 = head1 == l1 ? l2 : l1;
        //
        ListNode curr1 = head1;
        ListNode curr2 = head2;
        ListNode pre = curr1;
        int currNum = 0;
        // 进位
        int carry = 0;
        // 处理交集
        while (curr2 != null){
            int sum = curr1.value + curr2.value + carry;
            carry = sum / 10;
            currNum = sum % 10;
            curr1.value = currNum;

            pre = curr1;
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        // 进位为0无需再处理
        if (carry == 0){
            return head1;
        }
        // 处理超出的部分
        while (curr1 != null){
            int sum = curr1.value + carry;
            carry = sum / 10;
            currNum = sum % 10;
            curr1.value = currNum;

            pre = curr1;
            curr1 = curr1.next;
        }
        if (carry != 0){
            pre.next = new ListNode(carry);
        }
        return head1;
    }

    private static int calcNodeLength(ListNode node) {
        int length = 0;
        while (node != null){
            length++;
            node = node.next;
        }
        return length;
    }

    private static void printNode(ListNode reverseNode) {
        while (reverseNode != null) {
            System.out.print(reverseNode.value + "->");
            reverseNode = reverseNode.next;
        }
        System.out.println();
    }

    public static class ListNode {
        private int value;
        private ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }
}
